package chart.shortest_path;

import chart.图的存储.AbstractGraph;
import chart.图的存储.AdjacencyMatrix;
import chart.图的存储.AdjacencyTable;
import chart.图的存储.Edge;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * 通过广度优先搜索来生成单源最短路径（一个顶点到其他顶点的最短路径）
 * <p>适用于无权图</p>
 * <p>算法要点：</p>
 * <p>distant[]：顶点到该顶点的距离</p>
 *
 * <p>因为求的是距离, 如果是非连通图, 从一个顶点出发, 到达不了其他非连通的路径</p>
 *
 * @author yezh
 * @date 2023/7/12 11:22
 */
public class BFS {

    public static void main(String[] args) {
        testAdjacencyMatrix();
        System.out.println();
        testAdjacencyTable();
    }

    private static void testAdjacencyMatrix() {
        // 时间复杂度: O(V * V), 需要遍历整个矩阵
        AbstractGraph graph = new AdjacencyMatrix(6, false);
        graph.createGraph(Edge.graphDFS());
        System.out.println(Arrays.toString(getDistance(0, graph)));
    }

    private static void testAdjacencyTable() {
        // 时间复杂度: O(V + E), 需要遍历顶点和边
        AbstractGraph graph = new AdjacencyTable(6, false);
        graph.createGraph(Edge.graphDFS());
        System.out.println(Arrays.toString(getDistance(0, graph)));
    }

    public static int[] getDistance(int vertex, AbstractGraph graph) {
        int n = graph.getV();
        int[] distance = new int[n];
        Arrays.fill(distance, -1);
        // 防止图中有环, 从而导致死循环
        boolean[] visited = new boolean[n];
        Deque<Integer> queue = new ArrayDeque<>(n);
        distance[vertex] = 0;
        visited[vertex] = true;
        queue.offer(vertex);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                vertex = queue.poll();
                for (Integer neighborVertex : graph.getNeighborVertex(vertex))
                    if (!visited[neighborVertex]) {
                        distance[neighborVertex] = distance[vertex] + 1;
                        visited[neighborVertex] = true;
                        queue.offer(neighborVertex);
                    }
            }
        }
        return distance;
    }

}
